package com.c2b.algorithm.leetcode.base;

import java.util.*;

/**
 * <a href='https://leetcode.cn/problems/destination-city/'>旅行终点站(Destination City)</a>
 * <p>给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。</p>
 * <p>题目数据保证线路图会形成一条不存在循环的线路，因此恰有一个旅行终点站。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
 *      输出："Sao Paulo"
 *      解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。
 *
 * 示例 2：
 *      输入：paths = [["B","C"],["D","B"],["C","A"]]
 *      输出："A"
 *      解释：所有可能的线路是：
 *          "D" -> "B" -> "C" -> "A".
 *          "B" -> "C" -> "A".
 *          "C" -> "A".
 *          "A".
 *          显然，旅行终点站是 "A" 。
 *
 * 示例 3：
 *      输入：paths = [["A","Z"]]
 *      输出："Z"
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= paths.length <= 100</li>
 *         <li>paths[i].length == 2</li>
 *         <li>1 <= cityAi.length, cityBi.length <= 10</li>
 *         <li>cityAi != cityBi</li>
 *         <li>所有字符串均由大小写英文字母和空格字符组成。</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/12/20 14:02
 */
public class LC1436DestinationCity_S {

    static class Solution {
        public String destCity(List<List<String>> paths) {

            // set：用于记录从哪些城市出发
            Set<String> set = new HashSet<>();
            for (List<String> path : paths) {
                set.add(path.get(0));
            }
            for (List<String> path : paths) {
                // 如果不存在从当前目的地出发的城市，则当前目的地即为终点
                if (!set.contains(path.get(1))) {
                    return path.get(1);
                }
            }
            return "";
        }

        public String destCity2(List<List<String>> paths) {
            Map<String, String> map = new HashMap<>();
            for (List<String> path : paths) {
                map.put(path.get(0), path.get(1));
            }
            String destinationCity = paths.get(0).get(0);
            while (true) {
                if (!map.containsKey(destinationCity)) {
                    return destinationCity;
                }
                destinationCity = map.get(destinationCity);
            }
        }
    }
}
